Batch 3 - Class 170 - Grape Codes (Binary) 2

• (Dudeney - 373) During a country ramble Mr. and Mrs. Softleigh found themselves in a pretty little dilemma. They had to cross a stream in a small boat which was capable of carrying only 150 lbs. weight. But Mr. Softleigh and his wife each weighed exactly 150 lbs., and each of their sons weighed 75 lbs. And then there was the dog, who could not be induced on any terms to swim. On the principle of "ladies first," they at once sent Mrs. Softleigh over; but this was a stupid oversight, because she had to come back again with the boat, so nothing was gained by that operation. How did they all succeed in getting across? The reader will find it much easier than the Softleigh family did, for their greatest enemy could not have truthfully called them a brilliant quartette—while the dog was a perfect fool.
• Answer: Sons cross together. One comes back, Father goes, other son comes back. Now again both sons go, one comes back, mother goes, other son come back. Now again, both sons go, and one comes back to get the dog.

• List all grape codes for number 6. Which of these is its binary code? Is the binary code unique, can you prove it? Does it always exist?
• It seems that the uniqueness can be proved intuitively. Assume that N is the smallest number which has two distinct binary code. There can't be an overlapping "1" in any place, because otherwise we can remove that "1" and arrive at a smaller number with two binary codes. Similarly, the rightmost digit in both can't be zero, otherwise we can divide the number by 2, and get to a smaller number with two binary codes. So one of the codes has rightmost digit 1 and other has 0, which means one representation is even and the other is odd, so both can't represent the same number.
• Find the binary code for number 50
• Which number has binary code 1|0|1|1|0  ?   1|1|0|1|1  ?
• List down binary codes for first twenty natural numbers. What do you notice about binary codes of odd numbers? even numbers? How about multiples of 4? 
• Can you figure out a divisibility rule for 3 basis binary codes?
• Someone has a curious way to arrive at binary code - start with the number written on rightmost bin. Then, halve it, and write on the next (to left bin). If the number was odd, put a grape in that bin. Continue doing this till you reach zero. Does this work? Why?
• Fun way to multiply - To multiply two numbers, keep halving one number and doubling the other number, till the first number gets to 1. Now cross out all rows where the first number was even. Add the rest of the rows. See below:

• Start from 6 grapes in rightmost bin, and explode the dots. Wherever you have a choice, pick any one option to explode. Whats the final configuration?
• Its the binary code for 6
• Why does this happen? Will it always happen?
• Do the above exercise again, but instead of choosing an option at any stage, work through all the options in parallel. What do you get?
• All the grape codes of 6. Will you always get all the codes? (Think about any grape codes and go back to all grapes in rightmost bin - will the reverse of this path be available in the forward process?)

• Do the above exercise starting with 12 grapes in rightmost box. Do you get all the 20 grape codes for 12?
• Can you go through all the grape codes through explosions and "un"explosions, without revisiting a grape code? (Start with all grapes in rightmost bin) - Notice that this is equivalent to finding a Hamiltonian Path.
• Why should such a path always exist? Can you think about even and odd numbers. For even go from N in rightmost bin to N/2|0 passing through all grape codes. (Hint: Try to use the breakup of N=12 into N=10 and N=6, and recursively attempt for each of those)

• (Mott 178) There are three piles with 3,5 and 7 counters respectively in them. At each turn, a player may draw any number of counters from one pile (or all counters from one pile). Whoever draws the last wins. Who wins and how?
• Answer: Express number of counters in each pile as powers of 2 (so first pile has 1 and 2, second has 1 and 4, third has 1, 2 and 4). If a player leaves piles so that each power of 2 is present twice across all piles combined, they will win. So in this case, the first player wins by taking 1 from any pile.